import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;
import java.util.Stack;

/**
 * 递归实现容易导致溢出。所以使用非递归实现
 * 一般使用BFS解决最短路径问题，DFS判断是否有解
 */
public class BfsAndDfsTemplate {
    /**
     * 栈深度优先，想象一棵树一条路走到底遍历
     * 栈是从栈头往下放的，是竖着的
     *
     * @param node
     */
    public void dfsWithStack(Node node) {
        if (node == null) {
            return;
        }

        Stack<Node> stack = new Stack<>();
        stack.add(node);
        while (!stack.isEmpty()) {
            Node treeNode = stack.pop();

            if (Objects.nonNull(treeNode.getRight())) {
                // 先压栈右子树，这样出栈的时候就是先出左子树
                stack.push(treeNode.getRight());
            }
            if (Objects.nonNull(treeNode.getLeft())) {
                stack.push(treeNode.getLeft());
            }
        }
    }

    /**
     * 队列广度优先,想象一棵树一层一层遍历
     * 队列从队尾往里放的，是横着的
     *
     * @param node
     */
    public void bfsWithQueue(Node node) {
        if (Objects.isNull(node)) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(node);
        while (!queue.isEmpty()) {
            Node root = queue.poll();

            if (Objects.nonNull(root.getLeft())) {
                queue.add(root.left);
            }
            if (Objects.nonNull(root.getRight())) {
                queue.add(root.right);
            }
        }
    }

    public static class Node {
        public int value; //节点值
        public Node left;  //左节点
        public Node right; //右节点

        public int getValue() {
            return value;
        }

        public Node getLeft() {
            return left;
        }

        public Node getRight() {
            return right;
        }

        public Node(int value, Node left, Node right) {
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
}

